package 图;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;

/**
 * 给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
 *
 * 如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。
 */
//思路，连通无环的树就是图
public class 以图判树 {
    public static void main(String[] args) {

    }

    public static boolean validTree(int n, int[][] edges){
        if(edges.length != n - 1){
            return false;
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < edges.length; i++) {
            list.get(edges[i][0]).add(edges[i][1]);
        }
        boolean[] visited = new boolean[n];
        if(hasCycle(list, 0, -1, visited)){
            return false;
        }
        //如果有哪一个值没有访问到。
        for (boolean v : visited){
            if(!v) return false;
        }
        return true;
    }

    public static boolean hasCycle(List<List<Integer>> adjList, int node, int parent, boolean[] visited){
        visited[node] = true;
        for (int neighbor : adjList.get(node)) {
            if(!visited[neighbor]){
                if(hasCycle(adjList, neighbor, node, visited)){
                    return true;
                }
            }else if(neighbor != parent){
                return true;
            }
        }
        return false;
    }

}
